public class ValidBrackets{
    public boolean isValid(String s) {
        if (s==null || s.length()%2 == 1) {
            return false;
        }
        Map<Character, Character> outPairs = new HashMap<Character, Character>();
        outPairs.put(')','(');
        outPairs.put(']','[');
        outPairs.put('}','{');
        Deque<Character> stack = new LinkedList<Character>();

        for (int i = 0; i < s.length(); i ++) {
            char x = s.charAt(i);
            if (outPairs.containsKey(x)) {
                if (stack.isEmpty() || stack.peek() != outPairs.get(x)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(x);
            }
        }
        return stack.size()==0;
    }
}